\section{Introduction}

Query answering under constraints is the problem of computing the answers to a query over an incomplete database w.r.t.\ a set of constraints \cite{Meyden1998}. Such a problem is relevant in a variety of scenarios, such as information integration \cite{Lenzerini2002} and data exchange \cite{Fagin2003}. Query answering under constraints can be solved via query rewriting: given a query $Q$ over a set of constraints $R$, one computes a query $Q'$ (which depends on $Q$ and $R$) such that, for every database instance $I$, the answers of $Q$ over $R$ and $I$ coincide with the answers of $Q'$ over $I$.
